#include <iostream>
#include <limits.h>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
#define MAX_VERTEX_NUM 20
/* 
*在该结构下，arcs为对应带正权有向图的邻接矩阵；vexs为顶点字符数组，用于确定顶点的位置；vexnum为顶点数，arcnum为边数
*/ 
struct Graph {
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	string vexs[MAX_VERTEX_NUM];
	int vexnum, arcnum;
};

/*
*实现顶点的定位
*/ 
int LocateVex(Graph G, string v) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vexs[i] == v) {
			return i;
		}
	}
	return -1;
}

/*
*输入数据构建带正权的有向图
*/ 
void CreateGraph(Graph *G) {
	cout << "请输入顶点数和弧数: " << endl;
	cin >> G->vexnum >> G->arcnum;
	cout << "请输入顶点: " << endl;
	for (int i = 0; i < G->vexnum; i++) {
		cin >> G->vexs[i];
		G->arcs[i][i] = 0;
	}
	for (int i = 0; i < G->vexnum; i++) {
		for (int j = 0; j < G->vexnum; j++) {
			if (i != j) {
				G->arcs[i][j] = INT_MAX;
			}
		}
	}
	for (int i = 0; i < G->arcnum; i++) {
		cout << "请输入边的两个顶点, from v1 to v2: " << endl;
		string v1, v2;
		cin >> v1 >> v2;
		int i1 = LocateVex(*G, v1);
		int i2 = LocateVex(*G, v2);
		cout << "请输入弧的权值: " << endl;
		cin >> G->arcs[i1][i2];
	}
}

/*
*输出邻接矩阵
*/ 
void Print(Graph G) {
	cout << "图的邻接矩阵是: " << endl;
	cout << "     ";
	for (int i = 0; i < G.vexnum; i++) {
		cout << setw(3) << G.vexs[i] << setw(3) << "|";
	}
	//cout << G.vexs[(G.vexnum - 1)];
	cout << endl;
	for (int i = 0; i < G.vexnum; i++) {
		cout << G.vexs[i] << "  ";
		for (int j = 0; j < G.vexnum; j++) {
			if (G.arcs[i][j] == INT_MAX) {
				cout << "|" << setw(5) << "∞";
			}
			else
				cout <<  "|" << setw(5) << G.arcs[i][j];
		}
		cout << "|" << endl;
	}
}

/*
*基于Dijkstra的最小路径算法，实现单源最短路径 
*/ 
int ShortestPath_DIJ(Graph G) {
	cout << "请输入想查询到其他点最短距离的起点: " << endl;
	string s0;
	cin >> s0;
	int v0 = LocateVex(G, s0);
	if (v0 < 0) {
		cout << "wrong!" << endl;
		return -1;
	}
	const int num = G.vexnum;
	vector<int> path[num];
	int ShortPathTable[num];
	bool final[num];
	for (int i = 0; i < G.vexnum; i++) {
		final[i] = false;
		ShortPathTable[i] = G.arcs[v0][i];
		if (ShortPathTable[i] < INT_MAX) {
			path[i].push_back(v0);
			path[i].push_back(i);
		}
	}
	ShortPathTable[v0] = 0;
	final[v0] = true;
	for (int i = 1; i < G.vexnum; i++) {
		int min = INT_MAX;
		int v = 0;
		for (int w = 0; w < G.vexnum; w++) {
			if (!final[w]) {
				if (ShortPathTable[w] < min) {
					min = ShortPathTable[w];
					v = w;
				}	
			}
		}
		final[v] = true;
		for (int w = 0; w < G.vexnum; w++) {
			if (!final[w] && G.arcs[v][w] < INT_MAX && min + G.arcs[v][w] < ShortPathTable[w]) {
				ShortPathTable[w] = min + G.arcs[v][w];
				path[w].clear();
				path[w] = path[v];
				path[w].push_back(w);
			}
		}
	}
	
	/*
	*输出起点到其它点的最短路径。如果可到达则输出最小路径，否则输出“can't reach!"
	*/ 
	for (int i = 0; i < num; i++) {
		if (i != v0) {
			if (ShortPathTable[i] == INT_MAX) {
				cout << "从源点" << G.vexs[v0] << "到终点" << G.vexs[i] << "can't reach！" << endl;
			}
			else {
				cout << "从源点" << G.vexs[v0] << "到终点" << G.vexs[i] << "的最短路径: " << endl;
				cout << G.vexs[path[i][0]];
				for (int j = 1; j < path[i].size(); j++) {
					cout << "->" << G.vexs[path[i][j]];
				}
				cout << endl;
				cout << "其最短长度为: " << endl;
				cout << ShortPathTable[i] << endl; 
			}
			cout << "----------------------------------" << endl;
		}
	} 
	return 1;	 
}